package Tree;

import java.util.Stack;

public class InvertTree {
    public static void main(String[] args) {

    }

    /**
     * 递归方法，翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root){
        if(root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
    public void swapChildren(TreeNode root){
        TreeNode tempNode = root.left;
        root.left = root.right;
        root.right = tempNode;
    }

    /**
     * 非递归方法翻转二叉树
     */
    public TreeNode invertTree1(TreeNode root){
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode current = stack.pop();

            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            // 将非空的左右子节点加入栈中
            if (current.left != null) {
                stack.push(current.left);
            }
            if (current.right != null) {
                stack.push(current.right);
            }

        }
        return root;
    }
}
